package mao.leetcode.others.leetcode98;

import java.util.Stack;

public class Solution {

    public static void main(String[] args) {
        System.out.println(Integer.MIN_VALUE);
        //[-2147483648,null,2147483647]
        int a = -2147483648;
        TreeNode node1 = new TreeNode(a);
        TreeNode node2 = new TreeNode(2147483647);
        node1.right = node2;
        isValidBST(node1);
    }

        //迭代法，其实就是中序遍历
       public static boolean isValidBST(TreeNode root) {
        long compare = Long.MIN_VALUE ;  //防止第一个数字出现int_min  value
        Stack<TreeNode> stack = new Stack<>();  //每个节点都要入栈
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.add(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            /*
              if (cur == null) continue; // 防止cur是由于cur=cur.right
             上面一句执行不到，如果cur=cur.right==null 前面一句会弹出一个有效的node
             */
            if (cur.val <= compare) return false;
            else compare = cur.val;
            cur=cur.right;
        }
        return true;
    }

    //错误写法
    public static boolean isValidBST_1(TreeNode root) {
        long compare = Long.MIN_VALUE ;  //防止第一个数字出现int_min  value
        Stack<TreeNode> stack = new Stack<>();  //每个节点都要入栈
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.add(cur);
                cur = cur.left;
            }
            cur = stack.pop();

            if (cur.val <= compare) return false;
            else compare = cur.val;
            if (cur.right != null ) cur=cur.right; //错误写法 没有跟新cur
        }
        return true;
    }
     public static class TreeNode {
        int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
}
